/* Kruskal.java */

import java.util.Hashtable;
import java.util.Arrays;
import graph.*;
import set.*;

/**
 * The Kruskal class contains the method minSpanTree(), which implements
 * Kruskal's algorithm for computing a minimum spanning tree of a graph.
 */

public class Kruskal {

  /**
   * minSpanTree() returns a WUGraph that represents the minimum spanning tree
   * of the WUGraph g.  The original WUGraph g is NOT changed.
   */
  public static WUGraph minSpanTree(WUGraph g) {
	  WUGraph minSpanTree = new WUGraph();
    Object[] v = g.getVertices();

    // Add all the vertices from g to new graph and build hashtable 
    // with objects as keys and integers as values. This will allow
    // us to look up a vertecies unique integer in a disjoint set 
    // in constant time:
    Hashtable<Object, Integer> vTable = new Hashtable<Object, Integer>();
    for (int i = 0; i < v.length; i++) {
      minSpanTree.addVertex(v[i]);
      vTable.put(v[i], new Integer(i));
    }

    // get list of edges and sort by weight:
    Edge[] edges = getEdges(g);
    Arrays.sort(edges);

    DisjointSets dSets = new DisjointSets(v.length);

    for (int i = 0; i < edges.length; i++) {
      Edge edge = edges[i];
      int v1, v2;
      v1 = vTable.get(edge.getV1());
      v2 = vTable.get(edge.getV2());
      if (dSets.find(v1) != dSets.find(v2)) {
        minSpanTree.addEdge(edge.getV1(), edge.getV2(), edge.getWeight());
        dSets.union(dSets.find(v1), dSets.find(v2));
      }
    }

    return minSpanTree;
  }

  /**
   * getEdges() returns a list of edges in the WUGrpah g.
   */
  private static Edge[] getEdges(WUGraph g) {
    Edge[] edges = new Edge[g.edgeCount()];
    Object[] v = g.getVertices();

    int eIndex = 0;

    for (int i = 0; i < v.length; i++) {
      Neighbors n = g.getNeighbors(v[i]);
      for (int k = 0; k < n.neighborList.length; k++) {
        boolean inList = false;
        for (int j = 0; j < eIndex; j++) {
          if (edges[j].isSameEdge(v[i], n.neighborList[k])) {
            inList = true;
            break;
          }
        }
        if (!inList) {
          edges[eIndex] = new Edge(v[i], n.neighborList[k], n.weightList[k]);
          eIndex++;
        }
      }
    }

    return edges;
  }
}
